package com.xieyong.leetcode;

import java.util.LinkedList;
import java.util.Queue;

public class Leetcode909 {
    public static void main(String[] args) {
        Leetcode909 leetcode909 = new Leetcode909();
        int[][] list = {{-1,-1,-1,-1,-1,-1},{-1,-1,-1,-1,-1,-1},{-1,-1,-1,-1,-1,-1},{-1,35,-1,-1,13,-1},{-1,-1,-1,-1,-1,-1},{-1,15,-1,-1,-1,-1}};
        int i = leetcode909.snakesAndLadders(list);
        System.out.println(i);
    }

//    算法有问题
//    public int snakesAndLadders(int[][] board) {
//        int[] list = getSnakes(board);
//        for(int i : list) {
//            System.out.print(i + ",");
//        }
//        System.out.println();
//        int res = dfs(list, 0);
//        return res;
//    }
//
//    public int[] getSnakes(int[][] board) {
//        int n = board.length;
//        int[] dx = new int[n * n];
//        int count = 0;
//        for(int i = n - 1; i >= 0; i--) {
//            if(i % 2 != n % 2) {
//                for(int j = 0; j < n; j++) {
//                    dx[count++] = board[i][j];
//                }
//            } else {
//                for(int j = n - 1; j >= 0; j--) {
//                    dx[count++] = board[i][j];
//                }
//            }
//        }
//        return dx;
//    }
//
//    public int dfs(int[] board, int index) {
//        if(index == board.length) {return 0;}
//        if(index >= board.length - 6 - 1) {
//            return 1;
//        }
//        System.out.println(index);
//        int mincount = Integer.MAX_VALUE;
//        for(int i = index + 1; i <= index + 6; i++) {
//            if(board[i] != -1) {
//                mincount = Math.min(mincount, dfs(board, board[i] - 1) + 1);
//            }
//            if(i == index + 6) {
//                mincount = Math.min(mincount, dfs(board, i) + 1);
//            }
//        }
//        return mincount;
//    }
//   使用题解
    public int snakesAndLadders(int[][] board) {
        int n = board.length;
        boolean[] vis = new boolean[n * n + 1];
        Queue<int[]> queue = new LinkedList<int[]>();
        queue.offer(new int[]{1, 0});
        while (!queue.isEmpty()) {
            int[] p = queue.poll();
            for (int i = 1; i <= 6; ++i) {
                int nxt = p[0] + i;
                if (nxt > n * n) { // 超出边界
                    break;
                }
                int[] rc = id2rc(nxt, n); // 得到下一步的行列
                if (board[rc[0]][rc[1]] > 0) { // 存在蛇或梯子
                    nxt = board[rc[0]][rc[1]];
                }
                if (nxt == n * n) { // 到达终点
                    return p[1] + 1;
                }
                if (!vis[nxt]) {
                    vis[nxt] = true;
                    queue.offer(new int[]{nxt, p[1] + 1}); // 扩展新状态
                }
            }
        }
        return -1;
    }

    public int[] id2rc(int id, int n) {
        int r = (id - 1) / n, c = (id - 1) % n;
        if (r % 2 == 1) {
            c = n - 1 - c;
        }
        return new int[]{n - 1 - r, c};
    }
}
